Datang dari New Zealand pada tahun 1770, Leftenan James Cook dalam HM Bark Endeavour ternampak darat di Point Hicks, lebih kurang 70 km barat Pulau Gabo, sebelum membelok ke timur dan utara mengikuti pantaiAustralia.

Kapal yang belayar dari United Kingdom ke Sydney biasanya melintasi Lautan Hindi dan Lautan Selatan, belayar mengelilingi Van Diemen's Land sebelum membelok ke utara ke destinasi mereka. Beberapa kapten memandang hamparan air antara Van Diemen's Land dan pantai timur New South Wales dan tertanya-tanya sama ada ia adalah teluk yang besar atau selat. Mereka yang terselamat dalam nahas Sydney Cove, rosak dalam pulau-pulau Kumpulan Furneaux, juga fikir ia mungkin selat.

Untuk menjernihkan persoalan ini, Gabenor John Hunter menghantar George Bass untuk menyemak dengan teliti pantai dengan kapal penangkap ikan paus. Selepas sampai ke Wilsons Promontory dan Western Port pada Januari 1798 cuaca buruk dan kekurangan peruntukan memaksanya kembali ke Sydney. Bass kembali dengan Matthew Flinders pada Disember 1798 dalam Norfolk dan belayar melalui selat itu, membuktikan kewujudannya.

Pada Disember 1800, Leftenan James Grant dalam HMS Lady Nelson, dalam perjalanan dari Cape Town ke Sydney, belayar melalui Selat Bass dari barat ke timur. Gabenor King, kecewa dengan kekaburan carta Grant, menghantarnya kembali untuk meninjau selat dengan lebih teliti. Cuaca buruk menghalang beliau daripada tetap meneruskan melebihi Western Port, di mana beliau tinggal selama lima minggu, menanam gandum, jagung, kacang, beras, kopi dan kentang pada Pulau Churchill luar Pulau Phillip.[11]

Pada 1801 Harbinger, di bawah John Black, merupakan kapal kedua yang belayar di Selat Bass dalam perjalanan ke Port Jackson. Beliau sampai ke pantai berhampiran Cape Otway pada 1 Januari 1801, kemudian melencong tajam barat daya ke hujung barat laut Pulau Gabenor King (sekarang Pulau King), yang Black namakan sempena Gabenor New South Wales, Philip Gidley King. Beliau kemudiannya belayar ke arah timur Wilsons Promontory. Meneruskan perjalanan sekitar hujung tanjung, Black menemui Hogan Group, yang dinamakan sempena pemilik kapal Michael Hogan. Harbinger tiba di Port Jackson pada 12 Januari 1801.[12]

Pada Januari 1802, Leftenan John Murray dalam Lady Nelson melawat Western Port dan memasuki Port Phillip pada 14 Februari. Beliau menamakan Arthur's Seat, meneroka Corio Bay dan secara rasmi mengambil alih teluk (yang dinamakan Port King) untuk Britain.

Tiga minggu kemudian penjelajah Perancis Nicolas Baudin belayar melalui selat itu dari timur ke barat dan adalah yang pertama untuk meninjau dengan sempurna pantai di sebelah barat. Pada bulan April 1802, kapal ekspedisi Perancis Le Naturaliste di bawah Jacques Hamelin meneroka kawasan di sekeliling Pulau Perancis, sebagai sebahagian daripada ekspedisi Baudinke Australia. Ia menamakan pulau itu Ile des Français, dan di-Melayukan sebagai Pulau Perancis.

Pada 26 April 1802, Flinders, tidak menyedari lawatan Murray, memasuki Port Phillip dalam Investigator, memanjat Arthur's Seat, mendayung ke Mornington dan menyeberang ke Semenanjung Bellarine dan memanjat You Yangs.

Pada Januari 1803 Pemangku Leftenan Charles Robbins dalam sekunar HMS Cumberland belayar tepat di Port Phillip. Bersama beliau pemangku juruukur am Charles Grimes, James Meehan dan tukang kebun James Fleming.[13] Di hujung teluk mereka menemui sungai dan mengikutinya ke hulu di mana ia kemudian terbahagi. Mereka mengikuti cabang barat dan menamakannya Sungai Saltwater (sekarang Maribyrnong) ke tempat yang kini Braybrook, dan kemudian cabang timur air tawar (Yarra) ke Dights Falls. Mereka mengadakan pertemuan mesra dengan Orang Asli tempatan dan kembali ke kapal mereka melalui Corio Bay. Mereka membuat kesimpulan bahawa tapak yang terbaik untuk penempatan ialah di air tawar di sebelah hujung utara teluk, tetapi tidak bersemangat tentang tanah dan potensi pertanian.